package horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @program: data_structures_algorithms
 * @description: 马踏棋盘问题
 * @author: lld
 * @create: 2020-11-19 19:42
 **/
public class Horse {
    private static int X;
    private static int Y;
    private static boolean visited[];//是否访问
    private static boolean finished;

    /**
     * @Description:
     * @Param: [chess, row, col, step]
     * @return: void
     **/
    public static void traversalChess(int[][] chess, int row, int col, int step) {
        chess[row][col] = step;
        visited[row * X + col] = true;//使用一维数组记录二维棋盘是否走过
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(col, row));
        sort(ps);//贪心算法排序
        while (!ps.isEmpty()) {
            //取出下一个可以走的位置
            Point p = ps.remove(0);
            if (!visited[p.y * X + p.x]) {//没有访问过
                traversalChess(chess, p.y, p.x, step + 1);
            }
        }
        if (step < X * Y && !finished) {//还没有走完
            chess[row][col] = 0;
            visited[row * X + col] = false;
        } else {
            finished = true;
        }
    }
    //对下一步的下一步个数非递减排序
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size()-next(o2).size();
            }
        });
    }
    /**
     * @Description: 能走的位置
     * @Param: [curPoint]
     * @return: java.util.ArrayList<java.awt.Point>
     **/
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //左上5
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //左上6
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //右上0
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //右上7
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //左下4
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //左下3
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //1
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //2
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int[][] chess = new int[X][Y];
        visited = new boolean[X * Y];
        long s = System.currentTimeMillis();
        traversalChess(chess, 5, 1, 1);
        long e = System.currentTimeMillis();
        System.out.println(e - s);
        for (int[] rows : chess) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }
}
